/**
 * @file Nov.java
 * @brief 文件简要说明
 * <p>
 * 文件详细说明
 * @author - 2024/11/11  贾思浩  创建初始版本
 * @version - 2024/11/11  V1.0  简要版本说明
 * @par 版权信息：
 * 2024 Copyright 北京鑫万佳科技发展科技有限公司 All Rights Reserved.
 */
package com.year_24;

import java.util.Arrays;

/**
 *
 * @brief 类简要说明
 *
 * 类详细说明
 *
 *@author
 *    - 2024/11/11  贾思浩  创建初始版本
 *
 */
public class Nov {

    // 241111
    // lt1547 切棍子最小成本
    public int minCost(int n, int[] cuts) {
        int l = cuts.length;
        Arrays.sort(cuts);
        int[] cutsN = new int[l + 2];
        cutsN[0] = 0;
        cutsN[l + 1] = n;

        for (int i = 0; i < l; i++) {
            cutsN[i + 1] = cuts[i];
        }
        // dp[i][j] 表示 以cutsN[i-1]为最左端，cutsN[j+1]为最右端的最小成本。
        int[][] dp = new int[l + 2][l + 2];
        for (int i = l; i >= 1; i--) {
            for (int j = i; j <= l ; j++) {
                dp[i][j] = i == j ? 0 : Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + dp[k + 1][j]);
                }
                dp[i][j] += cutsN[j + 1] - cutsN[i - 1];
            }
        }
        return dp[1][l];
    }
    // lt312 戳气球
    public int minCoins(int[] nums) {

        return 1;
    }






    public static void main(String[] args) {

        System.out.println(new Nov().minCost(7, new int[]{1, 3, 5}));
    }
}
